1. Field of the Invention
The present invention relates to a multisignature method in which a plurality of signers successively perform a signature generating process with respect to a certain document to thereby generate one signature, apparatus, program, and system.
2. Description of the Related Art
In general, a cryptosystem can be classified into two types: a common key cryptosystem; and a public key cryptosystem. The public key cryptosystem has an advantage that a necessity for key distribution raising problem in a common key system is obviated.
For example, in the public key cryptosystem, users A, B, . . . generate a set of a public key and a secret key, and register the public key in a public list. The respective users A, B, . . . may prepare one set of keys regardless of the total number of users. At the time of use, for example, the user A generates a ciphertext using the public key of the user B in the public list, and transmits the ciphertext to the user B. The user B decodes the received ciphertext with self secret key. Thus, the public key cryptosystem obviates the necessity for the key distribution between the users A, B. Examples of a representative public key cryptosystem include a Rivest-Shamir-Adleman (RSA) cryptosystem, an ElGamal cryptosystem, an elliptic curve cryptosystem and the like.
In the above-described public key cryptosystem, a trapdoor one-way function is utilized. The trapdoor one-way function is such a function that operation in a certain direction can be easily executed, whereas it is difficult to execute operation in an opposite direction without any confidential information.
Therefore, the public key cryptosystem has a property that an arbitrary user can easily execute the generation of the ciphertext (operation in the certain direction) using the public key in the public list, and a property that it is difficult to execute the decoding of the ciphertext (operation in the opposite direction) without any secret key.
When the properties are used in a manner opposite to that of the cryptosystem, a signature system is realized. In the signature system, an only signer who has confidential information can generate a signature which can be verified by the third party. For example, the respective users A, B, . . . generate a set of the public key and the secret key, and register the public key in the public list. At the use time, for example, the user A generates a signature from the document using the self secret key, and transmits the document and the signature to the user B. The user B allows the public key of the user A in the public list to act on the signature and the document, and verifies validity of the signature. Examples of a representative signature system include RSA signature, digital signature algorithm (DSA), elliptic curve digital signature algorithm (ECDSA) and the like.
Examples of a technique to which such signature system is applied include a multisignature system. In the multisignature system, a plurality of signers successively perform a signature generation process with respect to a certain document, and generate one signature. The multisignature system is considered, for example, as a technique which electronically realizes a system for circulating the document in an organization to successively put approval seals.
As a technique which brings about an effect similar to that of the multisignature system, a concatenating signature system is considered in which the respective signers generate signatures with respect to a certain document, and the obtained respective signatures are concatenated together.
Here, the multisignature system refers to a system in which a size of the generated multisignature can be set to be smaller than that of the concatenated signature. Next, outlines of the multisignature system and the concatenating signature system will be described. FIG. 1A shows the outline of the multisignature system, and FIG. 1B shows the outline of the concatenating signature system.
In FIG. 1A, User 1 who is a first signer generates Signature 1 with respect to Document x, and thereafter sends Document x and Signature 1 to User 2 who is a second signer. User 2 generates “Signatures 1•2” utilizing Signature 1 as the signature with respect to Document x. “Signature 1•2” is a signature which assures that Users 1, 2 have both approved Document x, and is generated with a size smaller than that of data obtained by concatenating Signature 1 of User 1 to Signature 2 of User 2. Subsequently, a similar operation is successively executed by User 3 who is a third signer to User N who is an N-th signer to thereby generate “Multisignature 1•2 . . . N”.
As shown in FIG. 2, validity of “Multisignature 1•2 . . . N” is verified. A device for verifying the multisignature executes a verification process with respect to Document x and “Multisignature 1 . . . N” based on public keys 1, . . . , N at the time of the generation of the multisignature, and accepts or rejects the multisignature in accordance with verification results.
In the multisignature system, several additional functions have been proposed. Examples of a representative function includes message flexibility, order flexibility, and order verifiability.
The message flexibility refers to a property that a plurality of users can update or change a message while generating the multisignature during circulation of the message. For example, as shown in FIG. 3, User 1 whose order is first generates Signature 1 with respect to Document x. User 2 whose order is second updates or changes Document x1, obtains Document x2 as difference information, and then generates “Signature 1•2” utilizing Signature 1 with respect to Documents x1 and x2. “Signature 1•2” ensures that User 1 has approved Document x1, and User 2 has approved Documents x1, x2. Subsequently, the users to User N who is the N-th signer similarly successively execute the updating or the changing Document x1 and signature generation to obtain “Multisignature 1 . . . N”.
The order flexibility refers to a property that signature order can be freely changed till a stage of signature generation.
The order verifiability refers to a property that the order of the signer can be verified in the verification process of the multisignature. When there is the order verifiability, a verifier can confirm that the second signer has approved the document, and the second signer has approved the signature process of the first signer with respect to the multisignature generated by N signers. It is to be noted that the multisignature system in the present specification comprises the message flexibility, the order flexibility and the order verifiability.
On the other hand, active and passive attack methods exist in the multisignature system. In the passive attack method, an attacker utilizes public information only, and forges the multisignature with respect to an arbitrary document. In the active attack method, the following conditions (i) to (iii) are satisfied in the process of the forging of the multisignature with respect to the arbitrary document utilizing the public information.
(i) The attacker can prepare own public key or a set of the public key and secret key based on another signer's public key, and participate in the multisignature system as a regular signer.
(ii) The attacker can receive signers' secret keys in collusion with some signers.
(iii) The attacker can ask an arbitrary regular signer to sign on the arbitrary document chosen by the attacker.
Moreover, in the active attack method, a signer who the attacker pretends to be, and a signer who colludes with the attacker will be referred to as illegal signers. A time when the signature output by the attacker is a forged signature indicates a time when at least one signer is not an illegal signer, and is not asked to generate the signature with respect to the document corresponding to the signature in a group of signers who are supposed to have participated in the signature.
Furthermore, in the active attack method, especially a method of setting own key using another signer's public key at the time of the generation of the key to thereby generate the multisignature without using any signer's secret key is known as adaptive insider attack.
This active attack method is an attack method more powerful than the passive attack method. Therefore, the constituting of a multisignature method which is safe even against the active attack method means that higher security can be assured.
With regard to this type of security, the multisignature system is classified into two systems. In a first system, difficulty in operation of discrete logarithm is regarded as a ground for the security, and the security is proved by concept of zero knowledge proof. Examples of a representative system include Ohta-Okamoto System, and Micali-Ohta-Reyzin System. The first system is characterized in that the size of the multisignature does not depend on the number of signers, and is equal to that of the signature by one signer, and costs of the signature verification process can be suppressed. However, since the grounds for the security are based on zero knowledge dialogue proof in the first system, efficiency of resolving is bad, and the system does not have any tight security. The tight security indicates that divergence between difficulty in operation for solving a certain problem and difficulty in operation for solving another problem is low.
In general, to indicate the security of the multisignature system, a problem to break a one-way property of a trapdoor one-way function is reduced to a problem to break the multisignature system. That is, when the multisignature system is broken, it is indicated that the one-way property of the trapdoor one-way function is broken, and the security of the multisignature system is proved.
In detail, it is indicated that the one-way property of the trapdoor one-way function is broken at a high probability, if the multisignature system is broken. In this case, difficulty in breaking the multisignature system is considered to be equal to that in breaking the one-way property of the trapdoor one-way function, represented by a discrete logarithm problem or an RSA problem. At this time, it can be said that the multisignature system has a tight security with respect to the one-way property of the trapdoor one-way function.
Conversely, it is said that the multisignature system does not have any tight security against the one-way property of the trapdoor one-way function if, even when the multisignature system is broken, the one-way property of the trapdoor one-way function is not broken only at a low probability.
Here, it is assumed that there are two systems whose security are based on a certain problem, one of the systems has a tight security with respect to the problem difficult to operate, and the other system does not have any tight security. In the system which does not have any tight security, to assure the security equal to that of the system having the tight security, a key having a larger size is used, and a problem occurs that operation cost and storage region are increased. The above-described first system corresponds to this.
On the other hand, in the classification of the multisignature system, the second system has the tight security, and therefore solves the problem of the first system. In detail, in the second system, the difficulty in operating prime factorization is regarded as the ground for the security. Representative examples include Mitomi-Miyaji system in which difficulty in operating the RSA problem is regarded as the ground for the security (S. Mitomi and A. Miyaji, “A General Model of Multisignature Schemes with Message Flexibility, Order Flexibility, and Order Verifiability”, IEICE Transaction of fundamentals, 2001, E-84-A, pp. 2488 to 2499), and Kawauchi-Tada system (K. Kawauchi and M. Tada, “On the exact security of multisignature schemes based on RSA”, The Eighth Australasian Conference Information Security and Privacy (ACISP 2003), Springer-Verlag, 2003, Lecture Notes in Computer Science 2727, pp. 336 to 349).
Here, in the system of Mitomi, et al., as shown in FIG. 4, i-th signer applies a hash function Hi to a document x, and inputs exclusive OR of the obtained hash value and the previous signature σi−1 into an RSA signature function to thereby obtain an i-th signature σi.
In the system of Kawauchi, et al., as shown in FIG. 5, an i-th signer applies a first hash function Hi to a document x, previous signature σi−1, and random number ri, and applies a second hash function Gi to the obtained first hash value wi to obtain a second hash value. Next, exclusive OR of the second hash value, and the previous signature σi−1 and random number ri is operated to obtain an operation result si. Furthermore, this operation result si and the first hash value wi are input into the RSA function to thereby obtain i-th signature σi.
In any case, unlike the first system based on zero knowledge dialogue proof, the second system has a tight security with respect to the difficulty in the operation of the RSA problem.
However, the security of the system of Mitomi, et al. is not sufficiently tight with respect to the difficulty in the operation of the RSA problem. Furthermore, in the system of Mitomi, et al., as signature order advances, the size of a signer's signature key needs to be increased. Therefore, there are a problem that the signature order of the signer is limited, a problem that an operation amount increases with an increase of the size of the signature key and the like. Furthermore, to eliminate the limitation of the order, there is a problem that each signer has to store and register keys having different sizes.
On the other hand, the security of the system of Kawauchi, et al. is sufficiently tight with respect to the difficulty in the operation of the RSA problem. However, in the system of Kawauchi, et al., in the same manner as in the system of Mitomi, et al., as the order advances, the size of the signer's signature key needs to be increased. Therefore, there are a problem that the order is limited, a problem that the operation amount increases with the increase of the size of the signature key and the like.
As described above, in the multisignature system, when the ground for the security is laid in the difficulty in the operation of the RSA problem as in the second system, the size of the key needs to be increased as the order advances. Therefore, there are a problem that the order is limited, a problem that the operation amount increases and the like.